Integrated circuits (“ICs”, often called “chips”) are typically grown on and etched into semiconductor substrates. The transistors that make up the majority of their circuitry are generally confined to a two dimensional plane on the surface of the substrate. Almost any integrated circuit design requires connections from transistors on one part of the substrate to transistors on other parts of the substrate. These transistors are connected by tiny metal wires. The wires are not free wires, but are rather laid down in rigid layers (wiring planes) over the transistors. Unlike the transistors, the wired connections can use three dimensions, moving among different wiring planes by use of “vias”. Vias are implements at which connections can pass from one layer to another.
The confinement of transistors to a single, two-dimensional plane means that connections through transistors alone cannot go over each other, but must instead go around. The freedom of wired connectors to change layers means that one wire can go over another wire, rather than going around it.
Configurable ICs are ICs that can be “programmed” to provide different integrated circuit configurations. Configurable ICs can be thought of as general purpose chips. The logical blocks within them can be re-assigned to different tasks as needed. For instance, acting as a logical “AND” gate in one set up and as a logical “OR” gate in another setup. The importance of the difference between transistor connections and wire connections to configurable ICs will be explained below.
The use of configurable ICs (e.g. field programmable gate arrays, “FPGAs”) has dramatically increased in recent years. Configurable ICs usually have logic circuits, interconnect circuits, and input/output (I/O) circuits. The logic circuits (also called logic blocks) are typically arranged as an internal array of circuits. These logic circuits are connected together through numerous interconnect circuits (also called interconnects). The logic and interconnect circuits are typically surrounded by the I/O circuits.
FIG. 1 illustrates an example of a configurable logic circuit 100. This logic circuit can be configured to perform a number of different functions. As shown in FIG. 1, the logic circuit 100 receives a set of input data 105 and a set of configuration data 110. The configuration data set can be stored in a set of SRAM cells 115. From the set of functions that the logic circuit 100 can perform, the configuration data set specifies a particular function that this circuit is to perform on the input data set. Once the logic circuit performs its function on the input data set, it provides the output of this function on a set of output lines 120. The logic circuit 100 is said to be configurable, as the configuration data set “configures” the logic circuit to perform a particular function, and this configuration data set can be modified by writing new data in the SRAM cells. Multiplexers and look-up tables are two examples of configurable logic circuits.
FIG. 2 illustrates an example of a configurable interconnect circuit 200. This interconnect circuit 200 connects a set of input data 205 to a set of output data 210. This circuit receives configuration data bits 215 that are stored in a set of SRAM cells 220. The configuration bits specify how the interconnect circuit should connect the input data set to the output data set. The interconnect circuit 200 is said to be configurable, as the configuration data set “configures” the interconnect circuit to use a particular connection scheme that connects the input data set to the output data set in a desired manner. Moreover, this configuration data set can be modified by writing new data in the SRAM cells. Multiplexers are one example of interconnect circuits.
FIG. 3 illustrates a portion of a prior art configurable IC 300. As shown in this figure, the IC 300 includes an array of configurable logic circuits 305 and configurable interconnect circuits 310. The IC 300 has two types of interconnect circuits 310a and 310b. Interconnect circuits 310a connect interconnect circuits 310b and logic circuits 305, while interconnect circuits 310b connect interconnect circuits 310a to other interconnect circuits 310a. In some cases, the IC 300 has hundreds or thousands of logic circuits 305 and interconnect circuits 310.
The arrangement of interconnect circuits illustrated in FIG. 3 allows configurations in which the output of one chosen logic circuit can be sent through a series of interconnect circuits to an input of any other single chosen logic circuit. The connection would be made though a succession of interconnect circuits. However, it is usually the case that multiple logic circuits must be made to connect to each other.
One reason that multiple logic circuits must be connected is that ICs commonly need to deal with multiple bit “words”, not just single bits. For example, a user might want to invert a 4-bit number, and then perform another operation on the resulting 4-bit number. Each logic circuit in the configurable IC can perform an operation on one bit, and then pass the result on to another logic circuit to perform the next operation.
Such a set of operations results in a “data path” that, in this example, is 4 bits wide. Each logic circuit does an operation on one data bit, so a 4-bit set of operations requires 4 logic circuits in a row. In order to perform a series of operations on a particular 4-bit set of data, all 4 bits must be sent to another row of 4 logic circuits. The simplest way of doing this is to send all 4 bits to the next row down.
Another way of doing this is shown in FIG. 4. In FIG. 4, the output from logic circuits 405a, goes through the interconnect circuits 410a and 410b to the inputs of logic circuits 405b. 
FIG. 4 demonstrates that in the prior art multiple logic circuits could be connected in parallel to multiple other logic circuits. However, this set of connections came at a price; because each interconnect circuit can only be used to make one connection at a time. Thus, the figure also shows that logic circuits 405c and interconnect circuits 410c are completely isolated from other circuits. The figure also shows that any circuits on opposite sides of the connected circuits can only connect to each other if they go around the connected block.
The problem of blocked circuits gets worse if a user wants to shift a data path over, as shown in FIG. 5. This figure shows an attempt to shift a 3-bit data path from the logic circuits shown in tile set 520a over to the logic circuits in tile set 520b. Unless otherwise noted a “tile set” in this specification defines a group of tiles in the diagram, and is not itself an actual physical object. Circuit 505a connects to circuit 505d, and circuit 505b connects to circuit 505e, but each interconnect circuit can only be used once. Each interconnect circuit used in those two connections is unavailable for making a connection between circuit 505c and circuit 505f. Once the path between those circuits reaches dead end 530, it has no available interconnect circuit to go to. In some cases, long routes could connect circuits 505c and 505f, rather than the path simply being blocked outright. The long route would use interconnect circuits that are outside the illustrated area (below those shown in FIG. 5). However, data following such a route would pass through a greater number of interconnect circuits than data following the routes shown in FIG. 5 and would thus take longer to reach the destination circuit than data following the illustrated routes. In addition to creating timing problems, such long routes also become more and more complicated the greater the number of tiles in the tile sets.
Other configurable ICs of the prior art attempted to solve this problem by making direct connections between interconnect circuits in distant rows or columns. Here, a direct connection is one which does not pass through any routing circuitry other than that associated with the individual logic circuits it connects. FIG. 6 shows available direct connections 610 between a group of circuits 620a and several groups of circuits 620b-620e below.
Having distant interconnects in the same row or column is only a partial solution. Often a user may want a long sequence of operations performed on a multi-bit set, each operation taking one logic circuit per bit. Vertical and horizontal direct connections still confine wide data paths to stay within one set of columns or rows, and if a large number of operations needs to be performed, there may not be enough available space in a set of columns to allow for individual rows to be skipped by long direct connections.
As FIG. 7 shows, because of the blocking effects of a row of occupied circuits, such a sequence of operations may result in a large section of the chip being occupied by a wall 730 of in-use circuits. With such a wall in place, circuit 705a has no path to reach circuit 705b. 
One type of circuitry found on some configurable ICs is memory circuitry, sometimes called “digital memory” or just “memory”. Digital memory is accessed according to a system of addresses and words. Memory typically has a set of n addresses which specify the location of memory words that are m-bits long (where m and n are integers). The total number of bits stored in such a memory is the product of the number of addresses (sometimes called the depth of the memory) and the length of the words (sometimes called the width of the memory. A memory with n addresses that is m-bits wide contains n times m bits of information.
Memory is typically accessed through memory “ports” that specify the address of the memory word to be read or written over. Such ports have pre-configured word widths. Digital circuits typically operate on some time scale, each operation of such circuits takes place in one time period, or “clock cycle”. A memory port can perform one access to a memory per clock cycle of the memory. One access means reading or writing one word to the memory.
Some memories have multiple ports. These ports enable the memory to be accessed multiple times per clock cycle. This allows data to be written to and read from the memory about twice as fast. However, multiple ports accessing the memory at the same time creates the possibility that two or more ports may try to read from or write to the same address at the same time. Attempts to write to the same address at the same time with multiple memory ports at best result in an ambiguous result about which port “wins” and has its word written to that address. Attempts to read the memory through one port and write to the memory from another port create an ambiguity about whether the word previously written in that address or the word currently being written to that address will be read from the memory.
Therefore, there is a need in the art for a configurable IC with behavioral descriptions for dealing with the issues raised by multiple ports accessing the same memory.